In typical public key cryptography systems, digital signature key pairs, having a private key and public key, are often used to authenticate a digital signature of a subscriber using a software application in order to confirm the identity of the sender of the message. A subscriber may generally be for example a network computer node, a software application or user in the security system. In addition to digital signature key pairs, encryption key pairs are also generally used to encrypt the data being sent from one subscriber to another subscriber within the computer network. Certificates are typically generated by a trusted certification authority for the public keys of the private/public key pair to certify that the keys are genuinely owned by a named subscriber. Standards, such as ISO 9594-8 available from the International Organization for Standardization, define typical certificate content.
In a network community, there may be a multitude of different certification authorities and many subscribers. Generally, each subscriber stores a certification authority public key to verify that a trusted certification authority issued the certificate. A public key certificate typically includes a user public key which is bound by the signature of the certification authority to the subscriber name, and other data including expiry data indicating the expiration date or period for the public key certificate. Each sender (subscriber) has a copy of its own certificate. To send an encrypted message, a sender may access a directory, such as an onboard client cache memory or other certificate storage medium to get a copy of an encryption certificate for a specified receiver. When receiving digitally signed data, a receiver obtains a signature verification certificate and determines from the obtained certificate whether the sender has a valid signature. Generally, for a certificate to be considered valid, the digital signature must be valid and there must be no existing expiration or revocation of the certificate by an associated certification authority. Hence, subscribers typically serve as certificate validation units and validate certificates before encrypting information to other subscribers. Similarly, the subscribers also need to verify signature verification certificates before using a public key to validate a subscriber's signature.
In computer network systems that employ cryptography, the certification authority, also referred to herein as the certificate issuing unit, typically issues certificates for subscribers that use the associated certification authority as the primary trusted server. Alternatively, in some systems a trusted subscriber may play the role of a CA in generating and signing certificates of other subscribers. In larger networks, the trust relationships between the certification authorities typically involve multiple certification authorities. Trust relationships between certification authorities determine how certificates issued by one certification authority may be utilized or verified by entities certified by distinct certification authorities such as those in other networks. Since public key certificates provide a mechanism for obtaining authenticated public keys, provided the verifier has a trusted verification public key of the certification authority which signed the certificate, trusted paths may be established and maintained among the certification authorities and hence subscribers in large computer networks. In the case of multiple certification authorities, a certificate verification unit, such as a subscriber, may wish to obtain an authentic public key by verifying a certificate signed by a certification authority other than one for which it originally possesses a trusted public key. In this case, the verifier may still verify a certificate signed by other certification authorities provided a chain of certificates can be constructed which corresponds to an unbroken chain of trust from the certification authority public key which the verification unit does trust, to the public key it wishes to obtain trust in.
Conventional cryptographic systems, such as many public key cryptography systems, typically use a distributed directory where all certificates and certificate revocation lists are duplicated so each subscriber in a system can access the directory to perform validation. Certificate chains correspond to directed trust paths, also known as certification paths, such as trust relationships among certification authorities where at least one certification authority (CA) has certified another certification authority. A certificate containing the public key of a certification authority is called a CA-certificate. A CA-certificate resulting from one CA certifying another CA is called a cross-certificate, and the process of creating such a certificate is called cross-certification. In this case the CA which signs the certificate is different from the CA whose public key appears within the certificate. A CA-certificate may be either a cross-certificate or a self-signed certificate (where the latter is a CA-certificate signed by the same CA whose public key is within the certificate). Unilateral certification occurs where one certification authority certifies another certification authority but reciprocal certification does not occur. Where a pair of certification authorities certify each other, this is referred to as mutual cross-certification. In this case, the two corresponding cross-certificates are called a cross-certificate pair.
To ensure validity of a subscriber's public key, so that a subscriber may receive or send information along a fully trusted path, the goal for a verification unit is to find a sequence of certificates corresponding to a certification path starting at the certification authority whose public key the subscriber trusts directly (i.e., an anchor certificate issuing unit), and ending at a target certification authority which has signed the certificate of the public key to be verified. If the search for trusted paths is carried out using conventional search techniques, such as breadth first or depth first techniques as known in the art (see for example page 215-218 and 239-244 in “Data Structures and Algorithms”, by Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, published in 1983 by Addison-Wesley, Reading, Mass., incorporated herein by reference), then a problem arises by way of reduced system performance when large numbers of certification authorities are in the community of interest, and many different combinations of links among certification authorities in various networks (or the same network) exist. In such systems, a verification unit may spend valuable processing time verifying all combinations of links to determine whether a trusted path has been maintained with the certification authority of the verifying verification unit and the certificate issuing unit that issued the target certificate. An inefficiency results when many of the steps involved in an exhaustive search which explores a large number of network nodes, for example in a breadth-first search, end up leading to untrusted or non-existent paths, and therefore unnecessarily consumed computational effort. For example, the validation unit typically has to find the certification paths every time a signed electronic document is received or any time an encryption occurs; checking a large number of possible certification authority paths can be unnecessary and can take long periods of time thereby decreasing the system performance. In large systems, the performance may be so impeded as to render the validation unit impractical.
Hierarchical chain trust structures with one way and/or mutual cross-certification among certificate issuing units typically have verification units verify in the following manner. Each entity or verification unit starts with a trusted public key, for example the public key of the certificate issuing unit which created its own certificate (anchor CA). The shortest trust chain from any entity is a path in the tree which travels upward from the parent to a least common ancestor of the entity and a target entity, and then onwards back down to the target entity. However, if any CA-certificate or cross-certificate in that particular path has been revoked, has expired, or does not meet policy constraints as required by the anchor CA, that path must be discarded and another trust chain must be sought. In addition, the trust relationships between certificate issuing units may not be strictly hierarchical, in which case other valid paths may exist. Therefore, substantial entity resources can be expended in analyzing all of the possible certification links where a network contains a large number of certification authorities.
Typically, a client engine or other unit that must validate a message from a sending unit, must typically search for, obtain and validate a chain of certificates required to validate a given end-user certificate for which typically requires the client engine to validate all certificates of issuing units that are trusted as determined by cross certificates. This can become an enormous task, particularly with large network systems. The client engine typically repeats this chain construction for each end-user certificate often with little memory of previous constructions. In addition, with conventional systems, when validating an end-user's certificate issued by, for example, a foreign certificate issuer (a certificate issuing unit that is not the validating unit's trust anchor), a client engine will construct a certificate chain from a suitable trust anchor to the end-user certificate. This generally involves retrieval and validation of each cross certificate in the certificate chain. This process is typically repeated for each end-user certificate. Although the client engine may cache cross certificates, and corresponding revocation information pertaining to those certificates, the retrieval, chain construction and validation of each cross certificate must typically still be performed by the client engine in order to validate an end user certificate. The caching operation may save the client engine some network accesses, but typically not the computational mode.
Accordingly, a problem arises since a client engine would be required to build a certificate chain in order to validate an end-user certificate. This can be time consuming, especially from a constrained client engine perspective, based on a potentially large computational and network access costs. In addition, the client engines typically may store the last chain construction but not store beyond the optional caching of cross certificates and corresponding revocation information. In a typical example, for the consecutive revocation of two end-user certificates verifiable using the same certificate chain, the client engine typically still rebuilds the certificate chain and validates each cross certificate from a cache of information when validating the second certificate.
Accordingly, a need exists for an improved method and apparatus for a more efficient end-user certificate validation in systems employing certificates and trusted paths.